/**
 * FileName: Exercise1745.c
 * ---------------------------------------------------------------------------------------------------------------------
 * 17.44 Use doubly-Vertexed adjacency lists with cross Vertexs as described in the text to implement a constant-time
 * remove edge function `GRAPHremoveE` for the adjacency-lists graph ADT implementation (Program 17.6).
 *
 * 17.45 Add a remove vertex function `GRAPHremoveV` to the doubly-linked adjacency-lists graph ADT implementation
 * described in the previous exercise.
 * ---------------------------------------------------------------------------------------------------------------------
 * 跟17.44相比，增加了`GRAPHremoveV`
 */
#include <stdio.h>
#include <stdlib.h>
#include "../../examples/chapter12/ST.h"
#include "../../examples/chapter17/GRAPH.h"

//顶点相关
typedef struct node* Vertex;
struct node {
    int v;
    Vertex next;
    Vertex prev;
    Vertex cross;
};

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    Vertex* adj;
};

//辅助函数声明
Vertex NEW(int, Vertex);
void GRAPHshow(Graph);
Item createItem(Key, Value);

//辅助函数实现
Vertex NEW(int v, Vertex next) {
    Vertex x = malloc(sizeof(*x));
    x->v = v;
    x->next = next;
    if (next != NULL) {
        next->prev = x;
    }
    x->prev = NULL;
    x->cross = NULL;
    return x;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    printf("%d vertices, %d edges\n", G->V, G->E);
    int v;
    Vertex t;
    for (v = 0; v < G->V; v++) {
        printf("%2d:", v);
        for (t = G->adj[v]; t != NULL; t = t->next) {
            printf(" %2d", t->v);
        }
        printf("\n");
    }
}

Item createItem(Key k, Value v) {
    Item newItem = malloc(sizeof(*newItem));
    newItem->key = k;
    newItem->value = v;
    return newItem;
}

//图操作函数实现
Graph GRAPHinit(int V) {
    int v;
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = (Vertex*) malloc(V * sizeof(Vertex));
    for (v = 0; v < V; v++) {
        G->adj[v] = NULL;
    }
    STinit(4);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    G->adj[v] = NEW(w, G->adj[v]);
    G->adj[w] = NEW(v, G->adj[w]);

    G->adj[v]->cross = G->adj[w];
    G->adj[w]->cross = G->adj[v];

    Key vKey = v*G->V+w;
    Value vValue = G->adj[v];
    Item vItem = createItem(vKey, vValue);

    STinsert(vItem);

    Key wKey = w*G->V+v;
    Value wValue = G->adj[w];
    Item wItem = createItem(wKey, wValue);
    STinsert(wItem);



    G->E++;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;

    Key vKey = v*G->V+w;
    Key wKey = w*G->V+v;

    Item vItem = STsearch(vKey);
    if (vItem == NULL) {
        return;
    }

    Vertex t = value(STsearch(vKey));

    if (t == NULL) {
        return;
    }
    if (t->prev == NULL) {
        G->adj[v] = t->next;
        if (t->next != NULL) {
            t->next->prev = NULL;
        }
    }else {
        t->prev->next = t->next;
        if (t->next != NULL) {
            t->next->prev = t->prev;
        }
    }
    Vertex cross = t->cross;
    if (cross->prev == NULL) {
        G->adj[w] = cross->next;
        if (cross->next != NULL) {
            cross->next->prev = NULL;
        }
    }else {
        cross->prev->next = cross->next;
        if (cross->next != NULL) {
            cross->next->prev = cross->prev;
        }
    }
    Item tItem = createItem(vKey, t);
    Item wItem = createItem(wKey, cross);
    STdelete(tItem);
    STdelete(wItem);
    free(t);
    free(cross);
    G->E--;
}
int GRAPHedges(Edge a[], Graph G) {
    int E = 0;
    int v;
    Vertex t;
    for (v = 0; v < G->V; v++) {
        for (t = G->adj[v]; t != NULL; t = t->next) {
            if (v < t->v) {
                a[E++] = EDGE(v, t->v);
            }
        }
    }

    return E;
}
Graph GRAPHcopy(Graph G) {
    //TODO
}
void GRAPHdestroy(Graph G) {
    //TODO
}

void GRAPHremoveV(Graph G, int v) {
    Vertex t = G->adj[v];
    while (t != NULL) {
        Vertex next = t->next;
        int w = t->v;
        Edge v2w = EDGE(v, w);
        GRAPHremoveE(G, v2w);
        t = next;
    }
    G->V--;
}

//测试函数声明
void test_show();
void test_removeV();

int main(int argc, char *argv[]) {
    // test_show();
    test_removeV();
    return 0;
}

//测试函数实现
void test_show() {
    int V = 13;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(0, 5);
    Edge edge2 = EDGE(5, 4);
    Edge edge3 = EDGE(7, 8);
    Edge edge4 = EDGE(4, 3);
    Edge edge5 = EDGE(0, 2);
    Edge edge6 = EDGE(9, 11);
    Edge edge7 = EDGE(0, 1);
    Edge edge8 = EDGE(11, 12);
    Edge edge9 = EDGE(5, 3);
    Edge edge10 = EDGE(9, 12);
    Edge edge11 = EDGE(9, 10);
    Edge edge12 = EDGE(6, 4);
    Edge edge13 = EDGE(0, 6);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);
    GRAPHinsertE(G, edge11);
    GRAPHinsertE(G, edge12);
    GRAPHinsertE(G, edge13);

    GRAPHshow(G);
}

void test_removeV() {
    int V = 13;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(0, 5);
    Edge edge2 = EDGE(5, 4);
    Edge edge3 = EDGE(7, 8);
    Edge edge4 = EDGE(4, 3);
    Edge edge5 = EDGE(0, 2);
    Edge edge6 = EDGE(9, 11);
    Edge edge7 = EDGE(0, 1);
    Edge edge8 = EDGE(11, 12);
    Edge edge9 = EDGE(5, 3);
    Edge edge10 = EDGE(9, 12);
    Edge edge11 = EDGE(9, 10);
    Edge edge12 = EDGE(6, 4);
    Edge edge13 = EDGE(0, 6);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);
    GRAPHinsertE(G, edge11);
    GRAPHinsertE(G, edge12);
    GRAPHinsertE(G, edge13);
    printf("Graph Init show:\n");
    GRAPHshow(G);

    GRAPHremoveV(G, 0);
    printf("---------------------------------------------------------\n");
    printf("Graph removeV 0 show:\n");
    GRAPHshow(G);
}
